package com.review.backpack_01;

public class BP03 {
    //3. 多重背包问题
    //限定每件物品的数量
    private int maxValue(int[] weight, int[] value, int[] num, int bagWeight) {

        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {//前半部分和01背包相同
                for (int k = 1; k <= num[i] && k * weight[i] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        return dp[dp.length - 1];
    }

    //优化
    private int maxValue2(int[] weight, int[] value, int[] num, int bagWeight) {

        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            int s = num[i];
            for (int j = 1; j <= s; s -= j, j <<= 1) {
                for (int k = bagWeight; k >= 0 && k >= weight[i] * j; k--) {
                    dp[k] = Math.max(dp[k], dp[k - j * weight[i]] + j * value[i]);
                }
            }
            if (s > 0) {
                for (int j = bagWeight; j >= s * weight[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - s * weight[i]] + s * value[i]);
                }
            }
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(new BP03().maxValue(new int[]{1, 2, 3, 4}, new int[]{2, 4, 4, 5}, new int[]{3, 1, 3, 2}, 5));//10
        System.out.println(new BP03().maxValue2(new int[]{1, 2, 3, 4}, new int[]{2, 4, 4, 5}, new int[]{3, 1, 3, 2}, 5));//10

    }
}
